package com.hanxiaozhang.allarrange;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈全排列〉
 *
 * @author hanxinghua
 * @create 2022/12/26
 * @since 1.0.0
 */
public class AllArrange {

    public static void main(String[] args) {

        int[] arr = new int[]{1, 2, 3};
        swapRecursion(0, arr);

    }




    /**
     * 交换位置递归
     * 思路：以1,2,3举例
     * 首先，处理第一个位置元素，它有三种位置交换可能：0<=>0、0<=>1、0<=>2
     * 然后，在第一个位置交换是0<=>0的情况下，处理第二个位置元素，它有两种位置交换可能：1<=>1、1<=>2
     * 再然后，在第一个位置交换是0<=>0，第二个位置交换是1<=>1的情况下，处理第三个位置元素，它有一种位置交换的可能：
     * 2<=>2，此时，已经处理最后一个位置的元素，证明交换结束，打印该结果：1,2,3
     * 在第一个位置交换是0<=>0，第二个位置交换是1<=>2的情况下，处理第三个位置元素，它有一种位置交换的可能：
     * 2<=>1，此时，已经处理最后一个位置的元素，证明交换结束，打印该结果：1,3,2
     * 在第一个位置交换是0<=>1的情况下，处理第二个位置元素，它有两种位置交换可能：1<=>1、1<=>2
     * 以此类推 ... ...
     *
     * @param index 交换位置
     * @param arr
     */
    public static void swapRecursion(int index, int[] arr) {
        // 交换位置 等于数组长度时，打印结果
        if (arr.length == index) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = index; i < arr.length; i++) {
            // 交换
            swap(i, index, arr);
            swapRecursion(index + 1, arr);
            // 恢复现场
            swap(i, index, arr);
        }
    }

    /**
     * 两个位置元素交换
     *
     * @param i
     * @param j
     * @param arr
     */
    public static void swap(int i, int j, int[] arr) {
        if (i == j) {
            return;
        }
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

}
